#include "graph_support/TestFlowGraph.h"

#include <vector>

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"

#include "graph_support/attributes/FlowEdgeAttributes.h"
#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/impls/compact/CompactGraph.h"
#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/utils/GraphTemplateUtils.h"

using namespace GRAPH_SUPPORT_NS::attributes;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::impls::compact;
using namespace GRAPH_SUPPORT_NS::alg::flow;

typedef VectorGraphTmpl<
		int,
		FlowEdgeAttributesTmpl< int >,
		stdext::hash< int >,
		stdext::equal_to< int >
		> FlowGr;
typedef FlowGr::EdgeAttributes EdgeAttributes;
typedef Dinic< FlowGr > IntDinic;

void TestFlowRevertedEdges()
{
	using namespace GRAPH_SUPPORT_NS::utils;

	int n = 10;
	std::vector< int > vertices( n );
	for ( int i = 0; i < n; i++ )
	{
		vertices[i] = i;
	}
	FlowGr gr( vertices, true );
	BOOST_CHECK( ! findEdge( gr, 1, 2 ) );
	BOOST_CHECK( ! findEdge( gr, 2, 1 ) );

	gr.addEdge( 1, 2, EdgeAttributes( 123 ) );
	BOOST_CHECK( findEdge( gr, 1, 2 ) );
	BOOST_CHECK( findEdge( gr, 2, 1 ) );
	boost::optional< FlowGr::GrEdgePtr > e12 = findEdge( gr, 1, 2 );
	boost::optional< FlowGr::GrEdgePtr > e21 = findEdge( gr, 2, 1 );
	if ( e21 && e12 )
	BOOST_CHECK_EQUAL(
			& ( e21.get()->getAttributes() ),
			& ( e12.get()->getAttributes().getRevertedEdgeAttributes() ) );
	if ( e21 && e12 )
	BOOST_CHECK_NE(
			& ( e12.get()->getAttributes() ),
			& ( e12.get()->getAttributes().getRevertedEdgeAttributes() ) );
}

void TestDinic()
{
	int n = 10;
	int srcVert = 0;
	int destVert = 1;
	std::vector< int > vertices( n );
	for ( int i = 0; i < n; i++ )
	{
		vertices[i] = i;
	}
	FlowGr gr( vertices, true );

	gr.addEdge( srcVert, destVert, FlowEdgeAttributesTmpl< int >( 5 ) );
	{
	IntDinic dinic( gr );
	dinic( srcVert, destVert );
	BOOST_CHECK_EQUAL( 5, dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( srcVert, destVert ) );
	BOOST_CHECK_EQUAL( -5, dinic.getFlow( destVert, srcVert ) );
	}

	gr.addEdge( srcVert, 2, FlowEdgeAttributesTmpl< int >( 10 ) );
	gr.addEdge( 2, destVert, FlowEdgeAttributesTmpl< int >( 3 ) );
	{
	IntDinic dinic( gr );
	dinic( srcVert, destVert );
	BOOST_CHECK_EQUAL( 8, dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( srcVert, destVert ) );
	BOOST_CHECK_EQUAL( 3, dinic.getFlow( srcVert, 2 ) );
	BOOST_CHECK_EQUAL( 3, dinic.getFlow( 2, destVert ) );
	}

	gr.addEdge( 2, 3, FlowEdgeAttributesTmpl< int >( 5 ) );
	gr.addEdge( 3, 4, FlowEdgeAttributesTmpl< int >( 5 ) );
	gr.addEdge( 4, destVert, FlowEdgeAttributesTmpl< int >( 5 ) );
	{
	IntDinic dinic( gr );
	dinic( srcVert, destVert );
	BOOST_CHECK_EQUAL( 13, dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( 8, dinic.getFlow( srcVert, 2 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 2, 3 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 3, 4 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 4, destVert ) );
	}

	gr.addEdge( srcVert, 5, FlowEdgeAttributesTmpl< int >( 15 ) );
	gr.addEdge( 5, 4 , FlowEdgeAttributesTmpl< int >( 15 ) );
	gr.addEdge( 3, 6, FlowEdgeAttributesTmpl< int >( 15 ) );
	gr.addEdge( 6, destVert, FlowEdgeAttributesTmpl< int >( 15 ) );
	{
	IntDinic dinic( gr );
	dinic( srcVert, destVert );
	BOOST_CHECK_EQUAL( 18, dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( srcVert, 5 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 5, 4 ) );
	BOOST_CHECK_EQUAL( 0, dinic.getFlow( 3, 4 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 3, 6 ) );
	BOOST_CHECK_EQUAL( 5, dinic.getFlow( 6, destVert ) );
	}
}
